"""
Generic Solver using backtracking.

It is possible to use forward checking and also define
the order of backtracking.

"""

from time import time

DEBUG = False

class Solution(dict):
    def __init__(self, param):
        if isinstance(param, list):
            for k in param:
                self[k] = None
        elif isinstance(param, dict):
            for k, v in param.items():
                self[k] = v
        else:
            raise TypeError('Expected list of variables or solution')

    def is_possible(self, rules):
        """ Check if Solution is possible by the domain rules. """
        for rule in rules:
            if not rule(self):
                return False
        return True

    def __nonzero__(self):
        """
        Check if all keys in a dict are set to a not None value.
        
        When all variables have a value: it is a solution.
        """
        return reduce(lambda a, b : a and (self[b] is not None), self.keys(), [True])

    def is_set(self, key):
        return self[key] is not None

    def undefined_keys(self):
        """ Get a list of undefined keys (which value is None). """
        return [ x for x in self.keys() if not self.is_set(x)]

    def step(self):
        if self.step:
            return self.step
        else:
            return -1

    def __str__(self):
        tmp = {}
        for k in self.keys():
            if self.is_set(k): tmp[k] = self[k]
        return str(tmp)
        

def bt(solution, domain, rules, fc=True, sort=None, break_on_solution=False):
    solutions = []
    bt.step = 0
    _bt.break_on_solution = break_on_solution
    _bt(solution, domain, rules, fc, solutions, sort)
    return solutions

def _bt(solution, domain, rules, fc, solutions, sort):
    """
    Backtracking solver.
    
    @param fc Using forward checking.
    @param sort Define variable selection order.
    """
    if DEBUG:
        print solution
    if _bt.break_on_solution:
        if solutions:
            return
    if not fc and not solution.is_possible(rules): return
    if solution:
        save_solution = Solution(solution)
        save_solution.step = bt.step
        solutions.append(save_solution)
        if _bt.break_on_solution:
            for k in solution.keys():
                solution[k] = None
    va = solution.undefined_keys()
    if not va: return
    va.sort(cmp=sort)
    key = va[0]
    for value in domain:
        solution[key] = value
        if fc and not solution.is_possible(rules):
            solution[key] = None
            continue
        _bt(solution, domain, rules, fc, solutions, sort)
        bt.step += 1
        solution[key] = None

def bs(solution, domain, rules, fc=True, sort=None, break_on_solution=False):
    solutions = []
    bs.step = 0
    _bs.break_on_solution = break_on_solution
    _bs([solution], domain, rules, fc, solutions, sort)
    return solutions

def _bs(current_level, domain, rules, fc, solutions, sort):
    """
    Backtracking solver.
    
    @param fc Using forward checking.
    @param sort Define variable selection order.
    """
    if DEBUG:
        print current_level
    if _bt.break_on_solution:
        if solutions:
            return
    if not current_level:
        return
    new_level = []
    for solution in current_level:
        if not fc and not solution.is_possible(rules): continue
        if solution:
            save_solution = Solution(solution)
            save_solution.step = bs.step
            solutions.append(save_solution)
            if _bt.break_on_solution:
                for k in solution.keys():
                    solution[k] = None
                return
        va = solution.undefined_keys()
        va.sort(cmp=sort)
        if not va: continue
        key = va[0]
        for value in domain:
            save_copy = Solution(solution)
            save_copy[key] = value
            if fc and not save_copy.is_possible(rules):
                continue
            new_level.append(save_copy)
    bs.step += 1
    _bs(new_level, domain, rules, fc, solutions, sort)

def __solve(name, f, *kargs):
    print '===', name, '===' 
    start_time = time()
    sols = f(*kargs)
    end_time = time()
    values = [ x.step for x in sols]
    values.sort()
    print 'Solutions: ', len(values)
    if sols:
        print 'First Solution:', sols[0]
        print 'First Solution (steps): ', values[0]
        print 'Last Solution (steps): ', values[-1]
    else:
        print 'No solutions found.'
    print 'Total steps:', f.step
    print 'Elapsed Time (s): ', end_time - start_time

def solve(name, *kargs):
    __solve(name + " (bt)", bt, *kargs)
    __solve(name + " (bs)", bs, *kargs)
